【题解】 [HEOI2013]SAO 组合数学+树形DP luoguP4099 | Qiuly's blog!

【题解】 [HEOI2013]SAO 组合数学+树形DP luoguP4099

Posted on | In | Comments:

$loj$ 上没有此题，$bzoj$ 上是权限题，对于不上 $yzoj$ 的我来说只能去洛谷做题了：转送门😄 。

我们先不考虑边的权值(<与>)，这样子 $n-1$ 条边组成的就是树了，很显然是需要我们求出这棵树的合法拓扑序的个数，考虑使用 $\rm{DP}$ ，对于边的方向(即<,>) ，我们分类讨论即可。

首先的一个想法就是设 $f_u$ 表示点 $u$ 的子树的合法拓扑序的总数，但是这个时候如何计算呢，对于一个 $u$ 的儿子 $v$ ，我们虽然知道 $u$ 和 $v$ 的攻克的前后关系，但是合并答案貌似并不好合并。这个时候我们增加一维 $j$ ，$f_{u,j}$ 表示 $u$ 的子树的所有合法拓扑序中 $u$ 在第 $j$ 位上的总状态数。

也就是说，对于一个必须在 $u$ 前面攻克的关卡 $v$ ，我们考虑枚举一个 $j$ ，$v$ 子树中 $j$ 个结点在合并 $u,v$ 后放到 $u$ 前面，另外 $sz_v-j$ 个放到 $u$ 后面，然后枚举一个 $k$ ，表示当前的 $v$ 排在 $v$ 子树的拓扑序中的第 $k$ 位，只有 $k\leq j$ 的时候 $v$ 才可以转移 $u$ ，因为这个时候 $v$ 在 $u$ 前面。

现在再来考虑$“$ $j$ 个结点放在 $u$ 前面 $”$ 的方案数和$“$ $sz_v-j$ 个结点放在 $u$ 后面的方案数$”$，这个显然可以用组合数算，合并 $v$ 的子树后，$u$ 的排名从 $i$ 变成了 $i+j$ ，也就是说我们需要将 $j$ 个乱序插入到 $u$ 前面 $i+j-1$ 个数中，方案数显然为 $C_{i+j-1}^{j}$ ，那么现在总节点数显然为 $sz_u+sz_v$ (现在 $sz_u$ 和 $sz_v$ 还没有并在一起) ，$u$ 后面理所当然有 $sz_u+sz_v-i-j$ 个位置，将 $sz_v-j$ 个数插进去的方案数显然为 $C_{sz_u+sz_v-i-j}^{sz_v-j}$ 个，这两个数再乘上 $f_{u,i}$ 和 $f_{v,k}$ 就好了，这一次合并后 $u$ 的位置显然到了 $i+j$ ，所以 $f_{u,i+j}$ 显然要加上这一组贡献。

经整理后的转移方程如下：

代码就是这样写：

1
2
3
4
for i=1 to sz[u]
    for j=1 to sz[v]
        for k=1 to j
            pls(f[u][i+j],f[u][i]*f[v][k]*C[i+j-1][j]*C[sz[u]+sz[v]-i-j][sz[v]-j])

这是 $n^3$ 的，过不去。考虑前缀和优化，几下 $f_v$ 的前缀和，最后的一层循环就可以直接丢掉了。

这个就是 $v$ 要在 $u$ 前面的情况，$u$ 在 $v$ 前面的情况和这个差不多，不过转移的时候 $j$ 就要从 $0$ 开始了，因为那个时候 $u$ 前面是可以不多放任何东西的，还有就是 $u$ 在 $v$ 前面的时候注意 $k\geq j$ 时才可以转移 !

最后的答案就是 $\sum\limits_{i=1}^{n} f_{1,i}$ 啦。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e3+9;
const int mod=1e9+7;

int head[N],cnt;
struct Edge{int nxt,to,val;}G[N<<1];
int C[N][N],f[N][N],pre[N][N],suf[N][N],sz[N],g[N];

void add(int u,int v,int w) {
    G[++cnt]=(Edge){head[u],v,w},head[u]=cnt;
    G[++cnt]=(Edge){head[v],u,w^1},head[v]=cnt;
}

namespace OI {
    void pls(int&x,int y) {x+=y;if(x>=mod)x-=mod;}
    template <typename _Tp> inline void IN(_Tp&x) {
        char ch;bool flag=0;x=0;
        while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
        while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
        if(flag) x=-x;
    }
}using namespace OI;

void dfs(int u,int fa) {
    sz[u]=f[u][1]=1;
    for(int l=head[u];l;l=G[l].nxt) {
        int v=G[l].to,w=G[l].val;
        if(v==fa) continue;
        dfs(v,u);
        memset(g,0,sizeof(g));
        if(w) {
            for(int i=1;i<=sz[u];++i)
                for(int j=1;j<=sz[v];++j)
                    pls(g[i+j],1ll*f[u][i]*pre[v][j]%mod*C[i+j-1][j]%mod
                    *C[sz[u]+sz[v]-i-j][sz[v]-j]%mod);
        } else {
            for(int i=1;i<=sz[u];++i)
                for(int j=0;j<=sz[v];++j)
                    pls(g[i+j],1ll*f[u][i]*suf[v][j+1]%mod*C[i+j-1][j]%mod
                    *C[sz[u]+sz[v]-i-j][sz[v]-j]%mod);
        }
        sz[u]+=sz[v];
        memcpy(f[u],g,sizeof(g));
    }
    pre[u][0]=suf[u][sz[u]+1]=0;
    for(int i=1;i<=sz[u];++i) pre[u][i]=(pre[u][i-1]+f[u][i])%mod;
    for(int i=sz[u];i>=1;--i) suf[u][i]=(suf[u][i+1]+f[u][i])%mod;
}

int solve() {
    memset(head,0,sizeof(head)),cnt=0;
    memset(f,0,sizeof(f));
    int n;IN(n);
    for(int i=1;i<n;++i) {
        int u,v;char sign;
        IN(u),sign=getchar(),IN(v);
        add(u+1,v+1,sign=='<'?0:1);
    }
    dfs(1,0);
    int ans=0;
    for(int i=1;i<=n;++i) pls(ans,f[1][i]);
    return ans;
}

int main() {
    /*预处理组合数*/
    for(int i=0;i<=N-2;++i) C[i][0]=1;
    for(int i=1;i<=N-2;++i)
        for(int j=1;j<=N-2;++j)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    int T;IN(T);
    while(T--) printf("%d\n",solve());
    return 0;
}

可能有人会问，如果 $u$ 的儿子 $v$ 下面的边全都是 $>$ ，并且 $u$ 连向 $v$ 的边也是 $>$ ，那么这个时候 $v$ 以及其子树的所有点都必须在 $u$ 前面完成，在转移的时候为什么可以 $“$ 提出 $j$ 个结点放到 $u$ 前面 $”$ 呢？

其实想想就可以明白，在向上统计答案的时候对于一个 $v$ 的儿子 $a$ ，我们只统计了合并后 $a$ 在 $v$ 前面的情况，同样在 $u$ 统计 $v$ 时也只是统计了合并后 $v$ 在 $u$ 前面的情况，所有我们也只是统计了 $“$ $a$ 在 $v$ 前面且 $v$ 在 $u$ 前面 $”$ 的情况，所有被统计的情况一定是合法的。

本文标题:【题解】 [HEOI2013]SAO 组合数学+树形DP luoguP4099

文章作者:Qiuly

发布时间:2019年05月06日 - 00:00

最后更新:2019年05月06日 - 18:07

原始链接:http://qiulyblog.github.io/2019/05/06/[题解]luoguP4099/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。